// 二分查找 - 利用数组的 二段性 解决问题，每次可以舍弃一段数据
// 经典在 有序数组中 找一个数/找一个数的插入位置 的问题，都可以使用二分查找
// 要求时间复杂度为 O(log n) 的题目，通常使用二分查找

// 例题 4：
// 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
// 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
// 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
//
//        示例 1：
//
//        输入：x = 4
//        输出：2
//        示例 2：
//
//        输入：x = 8
//        输出：2
//        解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
//
//        提示：
//
//        0 <= x <= 231 - 1

// 解题思路：
// 本题虽然也是求 x 的算术平方根，本质上也还是在 0 ~ x 区间上找一个数，保证 ret * ret <= target 即可
// 右中点：mid = left + (right - left + 1) / 2
// x <= target: left = mid;
// x > target: right = mid - 1

public class MySqrt {
    public int mySqrt(int x) {
        long left = 0; long right = x;
        while(left < right){
            long mid = left + (right - left + 1) / 2;
            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return (int)left;
    }
}
